#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "trie.h" 

void string_reversing(char a[], int len)
{
	char b;
	int i;
	for (i=0; i<(len-1)/2; i++)
    {
        b=a[i];
		a[i]=a[len-2-i];
        a[len-2-i]=b;
    }
}

Trie * trie_create(Destructor dtor)
{
	Trie* tr;
	int i;
	tr=(Trie*)malloc(sizeof(Trie));
	tr->key = NULL;
	tr->par=NULL;
	tr->dtor=dtor;
	tr->data=NULL;
	tr->end=0;
	tr->childs=(Trie**)malloc(sizeof(Trie*)*256);
	for(i=0; i<256; i++)
	{
		tr->childs[i]=NULL;
	}
	return tr;
}

int trie_has(Trie * tr, const uchar * key)
{
	unsigned i=0;
	Trie* buftr;
	buftr = tr;
	while(1)
	{
		if(key[i]!='\0')
		{
			if(buftr->childs[(int)key[i]]!=NULL)
			{
				buftr=buftr->childs[(int)key[i]];
				i++;
			}
			else
			{
				return 0;
			}
		}
		else
		{
			if((buftr->end)!=0)
			{
				return 1;
			}
			else
			{
				return 0;
			}
		}
	}
}

Pointer trie_get(Trie * tr, const uchar * key)
{
	unsigned i=0;
	Trie* buftr;
	buftr = tr;
	while(1)
	{
		if(key[i]!='\0')
		{
			if(buftr->childs[(int)key[i]]!=NULL)
			{
				buftr=buftr->childs[(int)key[i]];
				i++;
			}
			else
			{
				return NULL;
			}
		}
		else
		{
			if((buftr->end)!=0)
			{
				return buftr->data;
			}
			else
			{
				return NULL;
			}
		}
	}
}

int trie_set(Trie * tr, const uchar * key, Pointer data)
{
	unsigned i=0;
	unsigned j;
	Trie* buftr;
	Trie* newtr;
	buftr = tr;
	while(1)
	{
		if(key[i]!='\0')
		{
			if(buftr->childs[(int)key[i]]!=NULL)
			{
				buftr=buftr->childs[(int)key[i]];
				i++;
			}
			else
			{
				newtr=(Trie*)malloc(sizeof(Trie));
				newtr->par=buftr;
				newtr->dtor=buftr->dtor;
				newtr->data=NULL;
				newtr->key=key[i];
				newtr->end=0;
				newtr->childs=(Trie**)malloc(sizeof(Trie*)*256);
				for(j=0; j<256; j++)
				{
					newtr->childs[j]=NULL;
				}
				buftr->childs[key[i]]=newtr;
				buftr=newtr;
				i++;
			}
		}
		else
		{
			if(buftr->data!=NULL)
			{
				if(tr->dtor!=NULL)
				{
					tr->dtor(buftr->data);
					buftr->data=data;
					buftr->end=1;
					return 1;
				}
				else
				{
					buftr->data=data;
					buftr->end=1;
					return 2;
				}
			}
			else
			{
					buftr->data=data;
					buftr->end=1;
					return	3;
			}
		}
	}
}

void trie_free(Trie * tr)
{
	unsigned i;
	if(tr!=NULL)
	{
		if(tr->dtor!=NULL)
		{
			tr->dtor(tr->data);
		}
		for(i=0; i<256; i++)
		{
			trie_free(tr->childs[i]);
		}
		free(tr);
	}
}

int trie_update(Trie * tr, const uchar * key, Updater up, Pointer next)
{
	unsigned i=0;
	unsigned j;
	Trie* buftr;
	Trie* newtr;
	buftr = tr;
	while(1)
	{
		if(key[i]!='\0')
		{
			if(buftr->childs[(int)key[i]]!=NULL)
			{
				buftr=buftr->childs[(int)key[i]];
				i++;
			}
			else
			{
				newtr=(Trie*)malloc(sizeof(Trie));
				newtr->par=buftr;
				newtr->dtor=tr->dtor;
				newtr->data=NULL;
				newtr->end=0;
				newtr->childs=(Trie**)malloc(sizeof(Trie*)*256);
				for(j=0; j<256; j++)
				{
					newtr->childs[j]=NULL;
				}
				buftr->childs[key[i]]=newtr;
				buftr=buftr->childs[key[i]];
				i++;
			}
		}
		else
		{
			up(buftr->data, next);
		}
	}
}

Trie * trie_get_node(Trie * tr, const uchar * key)
{
	unsigned i=0;
	Trie* buftr;
	buftr = tr;
	while(1)
	{
		if(key[i]!='\0')
		{
			if(buftr->childs[(int)key[i]]!=NULL)
			{
				buftr=buftr->childs[(int)key[i]];
				i++;
			}
			else
			{
				return NULL;
			}
		}
		else
		{
			if((buftr->end)!=0)
			{
				return buftr;
			}
			else
			{
				return NULL;
			}
		}
	}
}

int trie_delete(Trie * tr, const uchar * key)
{
	unsigned i=0;
	unsigned j;
	Trie* buftr;
	buftr = tr;
	while(1)
	{
		if(key[i]!='\0')
		{
			if(buftr->childs[(int)key[i]]!=NULL)
			{
				buftr=buftr->childs[(int)key[i]];
				i++;
			}
			else
			{
				return 0;
			}
		}
		else
		{
			if(tr->dtor!=NULL)
			{
				free(buftr->data);
				buftr->end=0;
			}
			else
			{
				buftr->end=0;
			}
			buftr=buftr->par;
			while(i>0 && buftr->end==0)
			{
				for(j=0; j<256; j++)
				{
					if((j!=(int)key[i]) && (buftr->childs[j] != NULL))
					{
						break;
					}
				}
				buftr->childs[(int)key[i]]=NULL;
				buftr=buftr->par;
				i--;
			}
			return 1;
		}
	}
}

void trie_traverse(Trie * tr, Enumerator en, void * user)
{
	unsigned i;
	char key[100] = "";
	char buf[2] =" ";
	Trie * buftr;
	if(tr!=NULL)
	{
		for(i=0; i<256; i++)
		{
			if(tr->childs[i]!=NULL)
			{
				if(tr->childs[i]->end==1)
				{
					buftr=tr->childs[i];
					while(buftr->par!=NULL)
					{
						buf[0]=buftr->key;
						strcat(key, buf);
						buftr=buftr->par;
					}
					string_reversing(key, strlen(key));
					en((const uchar*)key, tr->childs[i], user);
				}
				trie_traverse(tr->childs[i], en, user);
			}
		}
	}
}